
struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
  ListNode *detectCycle(ListNode *head) {
    if (head == nullptr) {
      return nullptr;
    }
    ListNode *slowPtr = head, *fastPtr = head;
    while (fastPtr->next != nullptr && fastPtr->next->next != nullptr) {
      fastPtr = fastPtr->next->next;
      slowPtr = slowPtr->next;
      if (fastPtr == slowPtr) {
        fastPtr = head;
        while (fastPtr != slowPtr) {
          fastPtr = fastPtr->next;
          slowPtr = slowPtr->next;
        }
        return fastPtr;
      }
    }
    return nullptr;
  }
};
